#include <stack>
#include <algorithm>
using namespace std;

// 思路： 使用两个栈，一个栈存储数据，另一个栈存储当前最小值
//      入栈时，数据栈入栈，最小值栈入栈当前值和栈顶最小值的较小值
//      核心点：就是push的时候，最小栈和数据栈同步入栈，pop的时候，两个栈同步出栈  -- 最小栈入是当前值和栈顶最小值的较小值
class MinStack
{
private:
    stack<int> _st;
    stack<int> _min_st;

public:
    MinStack()
    {
    }

    void push(int val)
    {
        _st.push(val);        // 数据栈入栈
        int temp = val;       // 当前值
        if (!_min_st.empty()) // 最小值栈不为空
        {
            temp = min(temp, _min_st.top()); // 取当前值和栈顶最小值的较小值
        }
        _min_st.push(temp); // 最小值栈入栈
    }

    void pop() // 同步出栈
    {
        _st.pop();
        _min_st.pop();
    }

    int top() //    返回数据栈栈顶元素
    {
        return _st.top();
    }

    int getMin() //  返回最小值栈栈顶元素
    {
        return _min_st.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */